package com.base.stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @ClassName: MinStack
 * @Description: 155. 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * push(x) —— 将元素 x 推入栈中。
 * pop()—— 删除栈顶的元素。
 * top()—— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/20 7:05 下午
 */
public class MinStack {
    private final int INIT_SIZE = 10;
    private int[] stack;
    private int min = Integer.MAX_VALUE;
    //初始状态；
    int tail = 0;
    public MinStack() {
        stack = new int[INIT_SIZE];
        Arrays.fill(stack,Integer.MAX_VALUE);
    }

    public void push(int val) {
        stack[tail] = val;
        tail++;
        if (tail == stack.length - 1) {
            doubleCapacity();
        }
        if (val<min){
            min = val;
        }
    }

    public void pop() {
        if (tail - 1 < 0) {
            return;
        }
        int remove = stack[tail - 1];
        stack[tail - 1] = Integer.MAX_VALUE;
        tail--;

        if (remove == min){
            reFindMin();
        }

    }

    public int top() {
        if (tail - 1 < 0) {
            return Integer.MAX_VALUE;
        }
        return stack[tail-1];
    }

    public int getMin() {
        return min;
    }

    private void doubleCapacity() {
        int[] newStack = new int[stack.length*2];
        Arrays.fill(newStack,Integer.MAX_VALUE);
        System.arraycopy(stack,0,newStack,0,stack.length-1);
        stack = newStack;
    }

    private void reFindMin(){
        int i = tail-1;
        min = stack[i];
        while (i>-1){
            if (stack[i]<min){
                min = stack[i];
                return;
            }
            i--;
        }
    }
}
